﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    void duplicateZeros(vector<int>& nums) {
        int n = nums.size();
        int cur, dest;
        for (cur = 0, dest = -1; dest < n-1;)
        {
            if (!nums[cur++])
                dest++;
            dest++;
        }//确定指针位置
        cur--;
        while (cur != -1)
        {
            if (nums[cur] == 0 && dest == n)
            {
                nums[--dest] = nums[cur--];
                dest--;
            }
            if (!nums[cur])
            {
                nums[dest--] = nums[dest--] = 0;
                cur--;
            }
            else
                nums[dest--] = nums[cur--];
        }
    }
};
//class Solution
//{
//public:
//    void duplicateZeros(vector<int>& arr)
//    {
//        // 1. 先找到最后⼀个数
//        int cur = 0, dest = -1, n = arr.size();
//        while (cur < n)
//        {
//            if (arr[cur]) dest++;
//            else dest += 2;
//            if (dest >= n - 1) break;
//            cur++;
//        }
//        // 2. 处理⼀下边界情况
//        if (dest == n)
//        {
//            arr[n - 1] = 0;
//            cur--; dest -= 2;
//        }
//        // 3. 从后向前完成复写操作
//        while (cur >= 0)
//        {
//            if (arr[cur]) arr[dest--] = arr[cur--];
//            else
//            {
//                arr[dest--] = 0;
//                arr[dest--] = 0;
//                cur--;
//            }
//        }
//    }
//};
int main()
{
    vector<int> dp(6,0);
    Solution().duplicateZeros(dp);
	return 0;
}